package demo.practice.bfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class P322 {
    public static void main(String[] args) {
        P322 p322 = new P322();
        p322.coinChange(new int[]{1}, 0);
    }

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.add(amount);
        Set<Integer> vis = new HashSet<>();
        vis.add(amount);
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                Integer poll = queue.poll();
                for (int coin : coins) {
                    if (poll == coin) {
                        return count + 1;
                    } else if (poll > coin && !vis.contains(poll - coin)) {
                        queue.add(poll - coin);
                        vis.add(poll - coin);
                    }
                }
                size--;
            }
            count++;
        }
        return -1;
    }
}
